﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace Search
{
    class BasicSearchEngine : ISearchEngine
    {
        private const int PARTIAL_MATCH_THRESH = 3;

        private String terms = null;
        private String[] data = null;
        private String partialMatch = null;
        private bool isPartialFound = false;

        public BasicSearchEngine()
        {
            //Copy and sort the data
            SortedList<String, String> names = new SortedList<String,String>();

            for (int i = 0; i < Data.names.Length; i++)
            {
                names.Add(Data.names[i], null);
            }

            data = names.Keys.ToArray();
        }

        bool ISearchEngine.IsPartialMatchFound
        {
            get { return isPartialFound; }
        }

        string ISearchEngine.GetPartialMatch()
        {
            return partialMatch;
        }

        void ISearchEngine.Search(String terms)
        {
            this.terms = terms;
        }

        IEnumerator<String> ISearchEngine.GetEnumerator()
        {
            if(terms == null)
                throw new NullReferenceException();

            LinkedList<LinkedList<String>> results = SearchExpressions(terms);

            foreach (LinkedList<String> items in results)
            {
                foreach (String s in items)
                {
                    yield return s;
                }
            }
        }

        private LinkedList<LinkedList<String>> SearchExpressions(String terms)
        {
            LinkedList<LinkedList<String>> results = new LinkedList<LinkedList<String>>();
            LinkedList<String> frontResults = new LinkedList<String>();
            LinkedList<String> midResults = new LinkedList<String>();
            LinkedList<String> lastResults = new LinkedList<String>();
            String s;

            isPartialFound = false;
            partialMatch = null;
            terms = terms.ToLower();

            for (int i = 0; i < Data.names.Length; i++)
            {
                s = data[i].ToLower();

                if (s.StartsWith(terms))
                {
                    frontResults.AddLast(data[i]);
                }
                else if (Regex.IsMatch(s, ".* +" + terms + ".*"))
                {
                    char[] delims = { ' ' };
                    String[] nms = data[i].Split(delims);
                    String nm = nms[nms.Length - 1] + ",";
                    for(int k = 0; k < nms.Length - 1; k++)
                        nm += " " + nms[k];
                    lastResults.AddLast(nm);
                }
                else if (terms.Length > 2 && Regex.IsMatch(s, ".*" + terms + ".*"))
                {
                    midResults.AddLast(data[i]);
                }

                if(terms.Length > 3 && LevenshteinDistance(s, terms) <= PARTIAL_MATCH_THRESH)
                {
                    isPartialFound = true;
                    partialMatch = s;
                }
            }

            results.AddLast(frontResults);
            results.AddLast(lastResults);
            results.AddLast(midResults);
            return results;
        }

        public int LevenshteinDistance(String s, String t)
        {
            int m = s.Length, n = t.Length;
            int cost;
            int[,] d = new int[m + 1, n + 1];

            for (int i = 0; i < m + 1; i++)
                d[i, 0] = i;
            for (int j = 0; j < n + 1; j++)
                d[0, j] = j;

            for (int i = 1; i < m + 1; i++)
            {
                for (int j = 1; j < n + 1; j++)
                {
                    if (s[i - 1] == t[j - 1])
                        cost = 0;
                    else
                        cost = 1;

                    d[i, j] = min(d[i - 1, j] + 1,
                                  d[i, j - 1] + 1,
                                  d[i - 1, j - 1] + cost);
                }
            }
   
            return d[m, n];
        }

        private int min(int a, int b, int c)
        {
            int min = a;
            if (b < min)
                min = b;
            if (c < min)
                min = c;
            return min;
        }
    }
}
